/*
https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/k-ge-bu-tong-zheng-shu-de-zi-shu-zu-by-l-ud34/
 */
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution992 {
    //此方法不是题解的方法，是自己想的
    public int subarraysWithKDistinct(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        Queue<int[]> queue=new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        int l=0;
        int ans=0;
        for (int i=0;i<nums.length;i++){
            map.put(nums[i],i);
            //注意，这里加上了很多虚假键值对
            queue.offer(new int[]{nums[i],i});
            if (map.size()>k){
                //应该确定应该去除哪个元素，优先队列中有很多虚假的键值对
                while (queue.peek()[1]!=map.get(queue.peek()[0])){
                    queue.poll();
                }
                int t=queue.poll()[0];
                l=map.get(t)+1;
                map.remove(t);
            }
            if (map.size()==k){
                //查询第一个合理元素的最后位置，首先应该剔除虚假的键值对
                while (queue.peek()[1]!=map.get(queue.peek()[0])){
                    queue.poll();
                }
                int t=queue.peek()[1];
                ans=ans+t-l+1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution992().subarraysWithKDistinct(new int[]{1, 2, 1, 2, 3}, 2));
    }
}
